1. Field of the Invention
The present invention relates to techniques for logic synthesis. More specifically, the present invention relates to a method and an apparatus for optimizing a logic network in a digital circuit.
2. Related Art
Rapid advances in computing technology presently make it possible to perform trillions of operations each second on data sets that are sometimes as large as a trillion bytes. These advances can be largely attributed to the exponential increase in the density and complexity of integrated circuits. High-density integrated circuits, such as a CPU chip, can have logic gate densities up to 500,000 gates per mm2, which makes it possible to implement many complex logical functions.
A logical function is performed by a group of interconnected logic gates, which is referred to as a “logic network”. Among the commonly used logic gates, exclusive-OR (hereinafter “XOR”) gates are widely used in arithmetic circuits, communications circuits, and coding schemes for error detection and correction. Particularly, XOR gates are commonly used in hardware implementations for Cyclic Redundancy Codes (CRC), which are designed to detect burst errors in data storage systems and communication applications. Specifically, a CRCn system can receive, check and validate a block of n-bit long binary data for transmission errors, and is able to detect single-bit and double-bit errors, odd numbers of errors, burst errors less than or equal to n-bit, and most burst errors greater than n-bits long.
For the previous example, a hardware implementation of the CRCn system typically uses a cascade XOR gate structure, which is also referred to as an “XOR-tree.” Note that for a system that implements CRCn there can be as many as n gate levels in the cascade structure, which may result in long gate delays. Furthermore, the cascade structure can miss redundant logic identification and removal in the XOR-tree and common logic sharing among the XOR-trees.
Normally, for an XOR-tree with a small number of inputs (typically less than eight), one can effectively convert it into a sum of product (SOP) representation, which facilitates optimizing the tree structure. However, an XOR-tree in SOP form has a size (number of cubes) that increases exponentially with the number of inputs. For example, a 16-input XOR-tree has a SOP representation of 215, or 32768 cubes in a flattened structure. Commonly, industrial EDA tools optimize the XOR-trees with large number of inputs using two methods: (1) balance the XOR-trees; and (2) do limited flattening. The first method can reduce gate delays by reducing gate levels, but can miss the common logic sharing. The second method can identify some of the logic sharing, but can not minimize the gate delays, and can not identify all the common logic sharing.
The XOR-tree optimization has been a difficult synthesis problem for a very long time. In the last two decades, powerful synthesis tools have been developed for AND-OR based logic networks. Unfortunately, so far no effective synthesis tool has been developed which can optimize an XOR logic network to minimize delay and chip area at the same time.
As a result, in the applications such as CRC, XOR logic has typically been implemented using cascade structures. Besides delay and speed problems, there are further problems. For example, it is also difficult to identify and remove redundant logic.
Hence, what is needed is a method and an apparatus for optimizing XOR-trees of any size and complexity in order to minimize delay and chip area without running into the above described problems.